class Solution:
    def maxProfit(self, prices) -> int:
        if len(prices) <= 1:
            return 0
        dp = [0] * len(prices)
        for i in range(1, len(prices)):
            for j in range(0, i):
                if j == 0 or j == 1:
                    dp[i] = max(dp[i], prices[i] - prices[j])
                else:
                    dp[i] = max(dp[i], dp[j - 2] + prices[i] - prices[j])
            if i >= 1:
                dp[i] = max(dp[i], dp[i-1])
        return dp[-1]


if __name__ == '__main__':
    so = Solution()
    m = [6,1,6,4,3,0,2]
    r = so.maxProfit(m)
    print(r)
